package com.demo.java.OD501_550.OD530;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【跳格子3(C卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146495907
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();  // 输入总数
        int[] nums = new int[n];

        // 读取每个元素的分数
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }

        int k = in.nextInt();  // 最大跳跃步数

        // 队列用来存储当前可选的得分
        int[][] queue = new int[n][2];
        int[] cache = new int[n];  // 缓存记录当前每个位置的最大得分

        // 初始化
        for (int i = 0; i < n; i++) {
            queue[i][0] = 0;
            queue[i][1] = 0;
            cache[i] = 0;
        }

        cache[0] = nums[0];  // 从起点的得分开始
        queue[0][0] = 0;
        queue[0][1] = cache[0];

        int index1 = 0;
        int index2 = 1;

        // 动态规划计算每个位置的最大得分
        int i = 1;
        while (i < n) {
            // 滑动窗口优化
            while (index1 < index2) {
                if (queue[index1][0] < i - k) {
                    index1 += 1;  // 弹出不在窗口内的元素
                } else {
                    break;
                }
            }

            // 计算当前元素的最大得分
            cache[i] = nums[i] + queue[index1][1];

            // 更新队列，维护一个递减的队列
            while (index1 < index2) {
                if (queue[index1][1] <= cache[i]) {
                    index1 += 1;
                } else {
                    break;
                }
            }

            queue[index2][0] = i;  // 当前元素位置
            queue[index2][1] = cache[i];  // 当前最大得分
            index2 += 1;  // 更新队列索引
            i += 1;
        }

        // 输出最终结果，即到达最后一个位置的最大得分
        System.out.println(cache[n - 1]);
    }
}